public class MaxHeap<E extends Comparable<E>> {
  private final Object[] data;
  private final int size;
  private int curr;

  public MaxHeap(int size) {
    this.size = size;
    this.data = new Object[size];
    curr = 0;
  }

  void swap(int i, int j) {
    Object temp = data[i];
    data[i] = data[j];
    data[j] = temp;
  }

  public boolean isEmpty() {
    return curr == 0;
  }

  public boolean ifFull() {
    return curr == size;
  }

  public int getSize() {
    return size;
  }

  @SuppressWarnings("unchecked")
  public boolean add(E e) {
    if (curr >= size) return false;
    data[curr] = e;
    // 比较curr和它的父节点，
    // 如果比父节点大则需要和父节点交换
    int child = curr;
    int parent;
    while (child > 0) {
      parent = (child - 1) / 2;
      if (((E) data[child]).compareTo((E) data[parent]) > 0) {
        swap(child, parent);
        child = parent;
      } else {
        break;
      }
    }
    curr++;
    return true;
  }

  @SuppressWarnings("unchecked")
  public E remove() {
    if (isEmpty()) return null;
    E r = (E) data[0];

    // 将最后一个元素放到0号位置
    data[0] = data[curr - 1];
    curr--;
    int parent = 0;
    // 从根节点开始， 如果比自己的大儿子小， 则和大儿子交换位置

    int leftChild = 1;
    int rightChild = 2;
    while (leftChild < curr) {
      // 找到大的那个儿子

      int bigBrother;
      if (rightChild >= curr) bigBrother = leftChild;
      else {
        bigBrother =
            ((E) data[leftChild]).compareTo((E) data[rightChild]) > 0 ? leftChild : rightChild;
      }
      if (((E) data[parent]).compareTo((E) data[bigBrother]) < 0) {
        swap(parent, bigBrother);
        parent = bigBrother;
        leftChild = (parent * 2) + 1;
        rightChild = leftChild + 1;
      } else {
        break;
      }
    }
    return r;
  }
}
